package algorithm.leetcode.I401to600;

/**
 * 题目有点费解
 * 首先需要返回 strs数组的最大子集的大小,显然如果没有约束条件那么最大子集大小就是 strs 的length
 * 因此,现在的约束条件是,子集中出现的 0 至多是 m 个, 1 至多是 n 个,如果考虑是 strs 本身的话 0 和 1 的数量大概率是超过这两个数字的
 *
 * 把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成
 * 不同点: 这里的目标值是能放进背包的字符串的数量, 而 0-1 背包问题是物品的总价值最大, 这个通过修改递推关系改变
 *        这里有两个约束, 而 0-1 背包问题只有1个约束, 通过两个dp数组 ** 这是不可以的,因为独立思考两个过程了,实际上是完全相关的
 */


// e.g. ["10", "0001", "111001", "1", "0"], 4, 3
//
//  "10":[1,1]   ==>  "0001":[3,1] ==> "111001":[4,2] ==>    "1":[0,1]  ==>    "0":[1,0]
//
//    0 1 2 3    ==>     0 1 2 3   ==>     0 1 2 3    ==>     0 1 2 3   ==>     0 1 2 3
//  0                  0                 0                  0   1 1 1         0   1 1 1
//  1   1 1 1    ==>   1   1 1 1   ==>   1   1 1 1    ==>   1   1 2 2   ==>   1 1 2 2 2
//  2   1 1 1          2   1 1 1         2   1 1 1          2   1 2 2         2 1 2 3 3
//  3   1 1 1          3   1 1 1         3   1 1 1          3   1 2 2         3 1 2 3 3
//  4   1 1 1          4   1 2 2         4   1 2 2          4   1 2 3         4 1 2 3 3
//

public class Q474 {

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];

        for (String str : strs) {
            int[] zeroAndOne = countZeroAndOne(str);

            // 递推
            int[][] backup = dp;
            dp = new int[m+1][n+1];

            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    if (i >= zeroAndOne[0] && j >= zeroAndOne[1]) {
                        dp[i][j] = Math.max(backup[i][j], backup[i-zeroAndOne[0]][j-zeroAndOne[1]] + 1);
                    }
                    // 二维时任意一维超出边界即不可实现,只能用上次结果移过来
                    else dp[i][j] = backup[i][j];
                }
            }

            // System.out.println("++++++++++++++++++");
            // for (int[] ints : dp) {
            //     System.out.println(Arrays.toString(ints));
            // }
        }

        return dp[m][n];
    }

    private static int[] countZeroAndOne(String str) {
        int[] cnt = new int[2];
        for (char c : str.toCharArray()) {
            cnt[c - '0']++;
        }
        return cnt;
    }

    public static void main(String[] args) {
        Q474 q474 = new Q474();
        System.out.println(q474.findMaxForm(new String[]{"10", "0001", "111001", "1", "0"}, 4, 3));
    }
}
